#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/7/26 12:43
# @USER    : Shengji He
# @File    : LongestIncreasingPathMatrix.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


# from collections import defaultdict

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        """
        Given an integer matrix, find the length of the longest increasing path.

        From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally
        or move outside of the boundary (i.e. wrap-around is not allowed).

        Example 1:
            Input: nums =
                [
                  [9,9,4],

                  [6,6,8],

                  [2,1,1]
                ]
            Output: 4
                Explanation: The longest increasing path is [1, 2, 6, 9].
        Example 2:
            Input: nums =
                [
                  [3,4,5],

                  [3,2,6],

                  [2,2,1]
                ]
            Output: 4
                Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

        :param matrix:
        :return:
        """
        if not matrix or not matrix[0]:
            return 0

        def helper(row, column, length):
            if (row, column) in path_dict:
                return length + path_dict[(row, column)]
            temp_ans = []
            if column + 1 <= columns - 1 and matrix[row][column + 1] > matrix[row][column]:
                temp_ans.append(helper(row, column + 1, 1))

            if row + 1 <= rows - 1 and matrix[row + 1][column] > matrix[row][column]:
                temp_ans.append(helper(row + 1, column, 1))

            if column - 1 >= 0 and matrix[row][column - 1] > matrix[row][column]:
                temp_ans.append(helper(row, column - 1, 1))

            if row - 1 >= 0 and matrix[row - 1][column] > matrix[row][column]:
                temp_ans.append(helper(row - 1, column, 1))
            if not temp_ans:
                path_dict[(row, column)] = 0
            else:
                path_dict[(row, column)] = max(temp_ans)
            return length + path_dict[(row, column)]

        path_dict = {}
        ans = 1
        rows, columns = len(matrix), len(matrix[0])

        for row in range(rows):
            for column in range(columns):
                ans = max(ans, helper(row, column, 1))

        return ans


if __name__ == '__main__':
    S = Solution()
    nums = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
    print(S.longestIncreasingPath(nums))
    print('done')
